# 单词拼写


class Solution:
    def wordBreak(self, s, wordDict):

        n = len(s)
        dp = [False] * (n + 1)

        dp[0] = True
        # 遍历单词的每一个字母
        for i in range(n):
            for j in range(i+1, n+1):
                # 寻找前半段存在的情况，逐渐由多个前半段拼接在一起
                if dp[i] and s[i: j] in wordDict:
                    dp[j] = True
        
        return dp[-1]
    

if __name__ == "__main__":
    s = "leetcode"
    w = ["leet","code"]

    sol = Solution()
    res = sol.wordBreak(s, w)
    print(res)

